-------<br />METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011)<br />-------<br />Workshop on Metric embeddings, algorithms and hardness of approximation<br />January 17-21, 2011<br />-------<br />Jan 19, 16:00-17:00<br />Ryan O'Donnell (Carnegie Mellon U.)<br />Inapproximability: A How-To Guide 3<br />-------<br />In this mini-course, I will introduce the area of approximability of<br />optimization problems and then discuss the methods used to prove<br />inapproximability results. We will assume the hardness of Label-Cover<br />and Unique-Games - these problems will be discussed in other<br />mini-courses.<br /><br />Key tools include the discrete Fourier transform and the notion of<br />"influences" for Boolean functions. As case studies, we will discuss<br />the Max-k-Coverage, Max-3Lin, and Max-Cut problems.
